package h0808;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 二叉树计算 ,根据前序中序求出原树,然后求和树,求和树的中序遍历序列.
 * @date 2024/8/8 17:05
 */
public class BinaryTreeSum {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //中序
        int[] inOrder = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //前序
        int[] preOrder = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //原始的二叉树
        TreeNode originRoot = buildTree(inOrder, preOrder);
        //和二叉树
        TreeNode root = buildSumTree(originRoot);

        //求出和二叉树的中序遍历序列
        List<Integer> res = new ArrayList<>();
        InOrder(res, root);
        System.out.println(res);
//        System.out.println(calculateSum(originRoot));
    }

    //思路 1.构建二叉树;
    //    2.构建求和的二叉树.  我这里采用的是使用求每个节点的左右子树的和,作为新节点的值.使用递归的方法
    //    3.然后求和树的中序遍历序列
    private static void InOrder(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        InOrder(res, root.left);
        res.add(root.val);
        InOrder(res, root.right);
    }

    //生成sumTree.
    private static TreeNode buildSumTree(TreeNode root) {
        //TODO
        if (root==null){
            return null;
        }
        int sum = calculateSum(root);
        TreeNode newNode=new TreeNode(sum);
        newNode.left=buildSumTree(root.left);
        newNode.right=buildSumTree(root.right);
        return newNode;
    }

    //计算一棵树左右子树的和,不包括根节点
    //这里时分别计算左右子树之和再相加
    private static int calculateSum(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftSum =subSum(root.left);
        int rightSum = subSum(root.right);
        return leftSum+rightSum;
    }

    //递归计算一棵树之和
    private static int subSum(TreeNode leaf) {
        if (leaf==null){
            return 0;
        }
        int leftSum=subSum(leaf.left);
        int rightSum=subSum(leaf.right);
        return leftSum+rightSum+leaf.val;
    }


    //1 2 3   2 1 3
    private static TreeNode buildTree(int[] inOrder, int[] preOrder) {
        if (inOrder.length == 0 && preOrder.length == 0) {
            return null;
        }
        int rootVal = preOrder[0];

        //构建根节点
        TreeNode root = new TreeNode(rootVal);

        int mid = 0;
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == preOrder[0]) {
                mid = i;
                break;
            }
        }

        //构建前序,中序左子树
        int[] leftInOrder = Arrays.copyOfRange(inOrder, 0, mid);
        int[] leftPreOrder = Arrays.copyOfRange(preOrder, 1, mid + 1);

        //构建前序,中序右子树
        int[] rightInOrder = Arrays.copyOfRange(inOrder, mid + 1, inOrder.length);
        int[] rightPreOrder = Arrays.copyOfRange(preOrder, mid + 1, preOrder.length);

        root.left = buildTree(leftInOrder, leftPreOrder);
        root.right = buildTree(rightInOrder, rightPreOrder);
        return root;
    }
}
